2007년04월14일 18번
[과목 구분 없음] 다음 함수 fib()를 사용하여 fib(5)를 실행했을 때 fib(5)를 포함한 fib( ) 함수의 총 호출 횟수와 최종 리턴 값으로 옳은 것은?
- ① 15, 5
- ② 15, 8
- ③ 20, 5
- ④ 20, 8
(정답률: 50%)
문제 해설
정답은 "15, 5"입니다.
fib(5)를 실행하면 fib(4)와 fib(3)이 호출됩니다. 이때 fib(4)를 계산하기 위해 fib(3)과 fib(2)가 호출되고, fib(3)을 계산하기 위해 fib(2)와 fib(1)이 호출됩니다. 이 과정에서 fib(2)는 중복 호출되므로, 이미 계산된 값을 저장해두는 메모이제이션(memoization) 기법을 사용하면 호출 횟수를 줄일 수 있습니다.
따라서, fib(2)는 한 번만 계산되고, fib(3)과 fib(4)는 각각 한 번씩 계산됩니다. 따라서 총 호출 횟수는 15번이 되며, 최종 리턴 값은 fib(5)의 값인 5가 됩니다.
fib(5)를 실행하면 fib(4)와 fib(3)이 호출됩니다. 이때 fib(4)를 계산하기 위해 fib(3)과 fib(2)가 호출되고, fib(3)을 계산하기 위해 fib(2)와 fib(1)이 호출됩니다. 이 과정에서 fib(2)는 중복 호출되므로, 이미 계산된 값을 저장해두는 메모이제이션(memoization) 기법을 사용하면 호출 횟수를 줄일 수 있습니다.
따라서, fib(2)는 한 번만 계산되고, fib(3)과 fib(4)는 각각 한 번씩 계산됩니다. 따라서 총 호출 횟수는 15번이 되며, 최종 리턴 값은 fib(5)의 값인 5가 됩니다.
